/*
* leetcode 143. 重排链表
*
给定一个单链表 L 的头节点 head ，单链表 L 表示为：
L0 → L1 → … → Ln - 1 → Ln
请将其重新排列后变为：
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
不能只是单纯的改变节点内部的值，而是需要实际的进行节点交换。
* */
/*
* */
import java.util.*;
class Solution {
    public void reorderList(ListNode head) {
        if(head.next==null||head.next.next==null)return;
        Stack<ListNode> stack=new Stack<>();
        int n=0;
        ListNode slow=head,fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        ListNode p=slow.next;
        slow.next=null;
        while(p!=null){
            stack.push(p);
            p=p.next;
        }
        p=head;
        while(!stack.isEmpty()&&p!=null&&p.next!=null){
            ListNode node=stack.pop();
            node.next=p.next;
            p.next=node;
            p=node.next;
        }

    }
}

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}